Multi-hop wireless networks (including mobile wireless multi-hop relay communication networks/systems) are emerging as a promising technology that has applications in metro-area Internet access. As used herein, “/” denotes alternative names for the same or similar components or structures. That is, a “/” can be taken as meaning “or” as used herein. In the present invention, infrastructure multi-hop wireless relay networks are considered. Infrastructure multi-hop wireless relay networks consist of one or more multi-hop relay base stations (MR-BSs), relay nodes/stations (RS) and mobile stations (MS)/end devices. Relay nodes are part of the network infrastructure and are connected to base stations to form a backhaul multi-hop wireless network. A base station may connect to other networks such as the Internet. The mobile stations/end devices associate with/connect to/attach to a MR-BS or RS to obtain network access.
In the prior art, a scheme to establish a unicast path between MR-BS and a RS was described. Referring now to FIG. 1 which is a schematic diagram of an exemplary multi-hop relay communication system, when RS1 enters the network, after conducting the initial ranging, a path P1 is established between MR-BS and RS1, P1={MR-BS, RS1}. FIG. 1 will be used to illustrate both how the prior art operated and how the present invention operates. A path identification (ID) is assigned to P1. When RS2 enters the network, a path P2 is established between MR-BS and RS2, P2={P1, RS2}. The path information is communicated to all the relay nodes (RSs) along the path. When MS1 enters the network, after the initial ranging, MR-BS knows that MS1 is associated with RS2, MR-BS binds MS1's basic and primary management connection identification (CID) to/with P2. MR-BS also notifies RS1 and RS2 to bind MS1's basic and primary management CID with/to P2. All the unicast traffic flows that start or end with MS1 have their CIDs bound with/to P2. For all the RSs in the system, there is a unique path that leads from MR-BS to each RS. For each MS in the system, their basic and primary management CID is bound to a path. For those MSs that connect directly to the MR-BS, P0={MR-BS}is defined and their CID is then bound to P0. It should be noted in the unicast scheme that a path can be bound to multiple CIDs, but each OD is only bound to one path.
Multicast and broadcast services (MBS) are very important for mobile wireless networks. In single-hop wireless communication systems, such as IEEE 802.16e, MBSs are associated With multicast and broadcast service flows. A multicast and broadcast service flow is not dedicated to a specific end device/mobile station/mobile device. For ease of notation, end devices are denoted as mobile stations (MSs) herein but it should be noted that end devices also include laptops, PDAs, cell phones, mobile terminals and any other such mobile devices. If one or more MSs send a request to the base station (BS) in order to receive multicast service, a multicast connection is instantiated for a multicast service flow, a connection identification (CID) number is assigned to this multicast connection. The BS then creates a multicast traffic connection with each MS requesting the multicast and broadcast service using the same CID. Each multicast service data unit (SDU) is transmitted only once by the BS, and all MSs requesting the multicast service are able to receive the SDU. Multicast SDUs are sent directly from the BS to the MSs, no multicast distribution tree needs to be established for single hop wireless communication systems.
When there are no relay stations, a request to add, change and delete a service between a base station and a mobile station is accomplished by the DSx signaling messages, DSx messages include DSA, DSC and DSD messages. When relay stations are added, the DSx messages are extended for communication between multihop relay base stations (MR-BS) and relay stations (RS), and between two relay stations (RS). The extension is transparent to the mobile stations (MS), so a MS does not understand the extended DSx messages. For clarification, an “*” is added at the end of a DSx message to indicate that this is a extended DSx message. A MR-BS and RS station can understand/interpret both DSx messages and extended DSx messages, represented by DSx*, but a mobile station (MS) can only understand DSx messages.
Multicast offers efficient utilization of network resources to deliver data from a source to multiple destination nodes. In a wireless multi-hop relay (MR) system, one or more relay stations (RS) may exist between a multi-hop relay base station (MR-BS) and a MS. When a MS associated with/attached to/connected to a RS joins a multicast application, multicast SDUs/packets/frames need to be forwarded from the MR-BS to the RS with which the MS is associated. Note that it is possible that only a subset of nodes in a wireless MR system may join a particular multicast service/group to transmit and receive the multicast SDUs for this multicast service. A multicast service/group has its own multicast connection ID (MCID) for communications among the multicast service members. One way to transmit SDUs/packets/frames from a MR-BS to one or more RSs is to broadcast the multicast SDUs/packets/frames to every RS in the network no matter whether they need to receive the packets/frames/SDUs or not. Another approach to solve the problem of how to transmit multicast SDUs/packets/frames from a MR-BS to RSs is to encapsulate multicast SDUs and unicast them individually to each of the RSs, that are associated with those MSs that have requested the multicast service. In this scheme, however, the MR-BS or the intermediate RS may need to transmit the same SDU multiple times, thus also incurring substantial cost in terms of bandwidth.
It would advantageous to have a method to establish and maintain a multicast distribution tree to distribute multicast SDUs/packets/frames along each branch of the multicast distribution tree. In this way, a multicast SDU is transmitted only once by a MR-BS to an RS and then only once by that RS to a further RS or to the MSs. The multicast SDU is transmitted only to the RSs associated with the MSs that have requested the multicast and broadcast service. Thus, the bandwidth utilization for multicast is improved.
The IP layer multicast routing protocols have been used to discover and establish the multicast tree for a multicast group in wired and wireless networks. The IP layer multicast routing protocols are based on the IP addresses. The Protocol Independent Multicast-Sparse Mode (PIM-SM) and the Protocol Independent Multicast-Dense Mode (PIM-DM) are two IP multicast routing protocols. PIM-DM employs a flooding and then pruning approach, which results in large overhead. PIM-SM employs a join/prune approach, which is more efficient in terms of network resource utilization. However, these protocols are designed for distributed and connectionless Internet communications, where the establishment and teardown of multicast tree routing is conducted by the multicast group members. In contrast, in the present invention, the establishment and teardown of multicast distribution tree routing is controlled by the base station (MR-BS).
Multicast routing protocols have also been proposed for wired or wireless mesh networks based-on layer 2 media access control (MAC) address. However, the establishment and teardown of multicast tree in these protocols is also distributively controlled by the multicast group members.
The network structure of a wireless multi-hop relay network is quite different from the wired Internet and wired or wireless mesh networks. In a multi-hop relay network, the MR-BS is a central control point. The multi-hop relay network has tree-type wireless connections with the BS as the root. The multi-hop relay network is a connection-oriented network, compared to mesh and connectionless wired or wireless networks. The SDUs/packets/frames are transmitted based on the connection ID, not the destination and source addresses as in wired or wireless mesh networks and Internet communications. The connection ID is dynamically assigned by the base station. The multicast routing protocols used for wired or wireless mesh networks and Internet communications are not applicable for a multi-hop relay network. Therefore, multicast mechanisms for wireless multi-hop relay networks are needed to establish, maintain, and tear down multicast distribution trees for efficient multicast communications using multicast connection ID.
In a multi-hop relay wireless communication network, a mobile station (MS) may connect to a MR-BS (base station) through one or more relay stations (RSs). To improve routing and data delivery efficiency, a path is established to connect the MR-BS to the MS. A path consists of the MR-BS and one or more intermediate RSs between the MR-BS and the MS. Multiple MSs may connect to the MR-BS using the same path. Each path is assigned a path_ID. When a service flow or a connection needs to be established between a MR-BS and a MS, a connection identifier (CID) is assigned to this connection. This CID is then bound to the path that connects the MS to the MR-BS so that the service flow can be activated. The binding between CID and path_ID can be updated or removed. The binding update and binding removal between CID and path_ID is accomplished by sending DSx* signals/messages along the path that connects the MR-BS and the corresponding MSs. A DSx* message includes DSA*, DSD* and DSC* signals/messages, where DS stands for dynamic service and “x” is used to denote A, D or C, where A stands for addition, D stands for deletion and C stands for change message. In the prior art, multiple CIDs can be bound, updated and removed to a single path_ID using a single DSx* message. In an earlier patent application, PU07066 filed mmddyy by the Applicants herein, a method and apparatus for establishing and maintaining a multicast tree using the existing DSx* messages was taught. In MBS services, a multicast CID (MCID) can be bound to multiple paths. The existing DSx* messages are not efficient for connection management in MBS services. For example, if a MR-BS wants to initiate a MBS for multiple MSs, or receives a MBS request from multiple MSs at about the same time, and these MSs connect to the MR-BS using different paths, it is necessary to send multiple DSA-REQ* or other DSx* messages to establish the multicast tree.